package leetcode.递归回溯BFSDFS;

import java.util.ArrayList;
import java.util.List;

/**
 * 17. 电话号码的字母组合
 */
public class Test17电话号码的字母组合 {


    public static List<String> letterCombinations(String digits) {
        List<String> ans = new ArrayList<String>();
        if (digits.length() == 0) {
            return ans;
        }
        String pattern = "";
        backtracking(pattern, digits, 0, ans);
        return ans;
    }

    /**
     * 比如输入1,2。对应的是abc,def。先从a开始，然后flag+1，依次向下遍历def，
     * 然后依次向上返回返回ad,ae,af，并且添加到结果集中，然后再向上返回到i=0的循环
     * 然后i+1，从b开始，再依次向下遍历def，如同a一样，依次返回所有结果，当所有的遍历完之和，返回到letterCombinations中结束。
     *
     * @param pattern 合法的字符组合串
     * @param digits  输入的键盘按键数字组合，借助他的长度可以验证 pattern 是否可以加入答案中
     * @param flag    索引，指向 digits 中的第几个数字
     * @param list    答案存储的地方
     */
    public static void backtracking(String pattern, String digits,
                                    int flag, List<String> list) {
        String[] alphabet = {"", "", "abc", "def", "ghi", "jkl",
                "mno", "pqrs", "tuv", "wxyz"};

        // 递归回溯的条件是，flag 指向最后一个数字
        if (flag == digits.length()) {
            list.add(pattern);
            return;
        }
        // 先获得数字对应的字符串，然后遍历它
        String str = alphabet[digits.charAt(flag) - '0'];

        for (int i = 0; i < str.length(); i++) {
                                                                // 第一次进入递归函数处理的是2，代表的字符是abc
                                                                // 第二次递归应该处理3，代表def
            backtracking(pattern + str.charAt(i), digits, flag + 1, list);
            // 若还有456数字的话，会接着递归下去，相当于自动实现多个 for 循环
        }
    }

    public static void main(String[] args) {
        String num = "23";
        System.out.println(letterCombinations(num));

        /**
         * 字符转整数！
         */
//        int num = '2'-'0';
//        System.out.println(num);

    }
}
